<!DOCTYPE html>
<html lang="zh-cn">
  <head>
    <meta charset="UTF-8">
    <title>Sucha's Blog - Archive for February, 2024</title>
    <meta name="generator" content="MarkdownProjectCompositor.lua">
    <meta name="author" content="Sucha">
    <meta name="keywords" content="suchang, programming, Linux, Lua">
    <meta name="description" content="Sucha's blog">
    <link rel="shortcut icon" href="../images/ico.png">
    <link rel="stylesheet" type="text/css" href="../styles/blog.css">
    <link rel="stylesheet" type="text/css" href="../styles/prism.min.css">
    <style id="site_theme"></style>
  </head>
  <body>
    <div id="body">
      <div id="text">
	   <!-- Page published by cmark-gfm begins here --><h1>Sucha's Blog ~ Archive for February, 2024</h1>
<p><a id="p0"></a></p>
<div class="date">24年2月25日 周日 12:12</div>
<h2>mmap(1)</h2>
<p>自从 cincau 支持多进程的方式之后，同步数据的能力最开始是通过不同 worker 的 UDP socket 来传递的，即时性有限，大概固定几秒钟去同步一次，而且如果数据量大了也是个问题。</p>
<p>相比较下，即时性的问题才是主要的，比如其中一个 worker 接受了用户的登陆状态，用户的下个请求是另外一个 worker 来服务的，此时 cookie 的 session 信息根本还没同步过来，就成了问题。</p>
<p>当然这个问题也有粗放的解决办法，比如用 SQLite 来同步，但是这种 Key/Value 的信息也使用 SQLite 觉得还是太重了。</p>
<p>这里插播一句，之前了解过使用 mmap 来同步数据的 <a href="https://github.com/Tencent/MMKV">MMKV</a>，因为 mmap 同样可以用来多进程同步数据，因此这个库也是可以多进程同步的，感觉这个库可以解决 95% 以上的同步问题，其他的例外情况，我下面会说。</p>
<p>在展开其他方案之前，我得检讨一下，一开始走了很多的弯路，虽然了解到需要使用一些多进程同步手段，比如最开始的 socket，比如可以使用 Linux 消息队列，以及 mmap，但是我把这个问题想得简单了，而且一开始我也没想起 MMKV。</p>
<p>比如我一开始就选择了 mmap，想做一个 mmap 的有序字典，我手头有 MIT LICENSE 的 AVL tree 代码，相比之下 MMKV 这种 bitcask 结构的数据库，是无序的，除非你 dump 出来所有的 key 再排序，否则你无法快速拿到按照 Key 排序的第一个节点，而 AVL tree 对 Key 排序的方案就可以。</p>
<p>可是已有的 AVL Tree 的方案，其对节点的引用是指针的，虽然 mmap 只管映射内存区域，但是不同的进程，其映射的内存区域很可能不一样，比如我使用的 LuaJIT，除了我自己主动调用的 mmap，其他不知道什么原因，也有不少的 mmap 调用。导致如果使用 AVL tree 的方案，除非是能保证每一个进程 mmap 过来给 AVL tree 使用的内存块，采用同样的起始地址，否则后续的指针计算，指向的节点地址就有问题。</p>
<p>虽然理论上，我可以将进程空间的一大段都交给这个 AVL tree 共享内存的方案，但是实际做起来其实也不方便，而且 mmap 这个系统调用其实很频繁，用 strace 就可以看到，其他的一些文章也有介绍。</p>
<p>所以，不得不将 AVL tree 的指针引用，改成 int32_t 的间接引用，这里的 int32_t 分成了高 16bit 和低 16bit，其中的高 16bit 用于 index 内存区块，低 16bit 用于 index 每个区块内的位置，byte offset。</p>
<p>之所以这么做，是因为内存块是动态申请的，不会一下就申请完所使用的内存，而是根据使用量逐步申请，虽说是共享内存，也总得使用实际内存空间的嘛。</p>
<p>另外这个 AVL tree 的方案相比 MMKV，其实有很大的限制，因为考虑到不想做 bitcask 那样的回收方案（简单点做），因此设置了限定最大的 Key/Value 长度，这个是调用库在初始化的时候就得进行设置的。</p>
<p>比如 Key/Value 的最大长度是 64 字节，其中 Key 是一个 timestamp 占 32 字节，后续的 Value 是一个 MD5 的 hash 占 32 字节，这里还可以插播一句，可以将这个 Value 作为 MMKV 的 Key，这样就实现了 MMKV Key 的有序，回应了最开始说的 95% 的应用场景。不过这里也得提一下，MMKV 还可以设置每个 Key 的过期时间，所以这个 95% 的应用场景，实际上还可以扩大不少。</p>
<p>回到刚刚的 AVL Tree，所有需要同步的数据都存放到 mmap 的内存区块中，每个进程都有对 AVL Tree 的引用，以及自己保留一份已经打开的内存区块列表，当别的进程因为塞入更多的数据申请了新的内存区块，其他进程在进入库调用的时候，检查到这个场景，将新的内存区块也 mmap 到自己的进程空间上。</p>
<p>因为每条数据是固定的长度（最大 Key/Value 长度），所以 AVL Tree 的 index 间接指针会忽略掉不同进程内存区块的起始地址不一致的情况，只关注内存区块的序号，以及每条数据对应内存区块的偏移字节，当这个内存区块已经映射到进程空间上后，对 index 的数据的读写就没有障碍了。</p>
<p>在实际使用中，当内存空间不足时，申请内存区区块序号（2^16个），映射内部的节点地址偏移，两者揉进每个节点的唯一 index，当删除节点时，节点可以回收而不需要整理内存区块，比如将该节点的 index 保存到未使用空间列表节点的 right 指针（间接指针）中。</p>
<p>上面说完了 mmap AVL Tree 的使用场景、面临的问题，提出的解决方案，和该方案的限制，下面列出来了一些实际跑通该场景的有趣细节：</p>
<ul>
<li>AVL Tree 需要对比 Key 才能排序然后旋转，但是这个比较函数的运行空间是在不同的进程地址空间，因此每个进程在实际进行查找、插入、删除时，得使用自己进程空间的比较函数来执行，如果比较函数的函数指针，用的是其他进程的，那就有问题了（父子进程不在此讨论范围）</li>
<li>mmap 有些参数需要注意，除了多进程共享一定会用到的 MAP_SHARED，还得使用 MAP_POPULATE，否则后续其他进程将内存区块加载进来后，会遇到问题，这个参数是告诉 mmap，为了避免后续访问地址的 page fault，得将此文件涉及到的内存地址，先全都映射上来</li>
<li>mmap 只涉及到共享的内存区块，为了保证数据的一致性，还得在访问时加锁，需要用到 pthread_mutexattr_setpshared 的 PTHREAD_PROCESS_SHARED，除此外，当某个进程 crash 掉而没有清理 pthread 数据时（共享的内存区块中），其他进程在锁的处理过程中，需要 pthread_mutex_consistent，这个是在初始化 mutex 时通过 pthread_mutexattr_setrobust 的 PTHREAD_MUTEX_ROBUST 参数保证的</li>
</ul>
<p>细节太多了，当然相比较 SQLITE，上述两套方案的效率会高很多。</p>
<p>MMKV 已经很成熟，多平台都能支持，AVL Tree 是我当初小看了 mmap 导致的，而且有先天的短板，虽然说提供了有序 Key 的能力，但这个是在约束了最大 Key、Value（每条数据都是这个最大长度）来达到的，因为可以避免替换 mmap 共享的内存区块。</p>
<div class="category"><a href="CategoryProgramming.html">CategoryProgramming</a> / <a href="2024-02.html#p0">Permalink</a> / <a href="https://github.com/lalawue/homepage/discussions/categories/blog" target="_blank">Discussion</a></div>
<!-- Page published by cmark-gfm ends here -->
  <div id="foot">2004-<script>var d = new
	Date();document.write(d.getFullYear())</script> &copy;
	Sucha. Powered by MarkdownProjectCompositor.
  </div>
  </div><!-- text -->
  <div id="sidebar">
  </div><!-- sidebar -->
  <script src="../js/prism.min.js" async="async"></script>
  <script src="../js/blog_sidebar.js"></script>
  </div> <!-- body -->
</body>
</html>